package leetcode100;

import java.util.Arrays;

public class lc019 {
    public static void main(String[] args) {
        int n = 7;
        int[] res = countBits(n);
        System.out.println(Arrays.toString(res));
    }

    public static int[] countBits(int n) {
        if (n==0) return new int[]{0};
        if (n==1) return new int[]{0,1};

        int[] res  = new int[n+1];
        res[0] = 0;res[1] = 1;
        int firstHalfIndex = 0;
        for (int i = 2; i <= n;) {
            System.out.println(Arrays.toString(res));
            firstHalfIndex=0;
            if (i*2<=n+1) {
                //                    System.out.println("if");
                for (int j = i; j < i*2; j++,firstHalfIndex++) {

                    res[j] = res[firstHalfIndex]+1;
                }
                i = i*2;
            } else {
//                System.out.println("else");
                for (int j = i; j <=n ; j++,firstHalfIndex++) {
                    res[j] = res[firstHalfIndex]+1;
                }
                break;

            }
        }
        return res;
    }
}
